package Tudy

import (
	"fmt"
	"sort"
)


func Tsmain()  {

	//NullSum:=[10]byte{} //代表空集合
	GraPh:=make(map[byte]map[byte]byte)  //DFA图
	//手动初始化DFA图
	for i:='1';i<='7';i++{
		GraPh[byte(i)]=make(map[byte]byte)
	}

	GraPh['1']['a']='6'
	GraPh['1']['b']='3'
	GraPh['2']['a']='7'
	GraPh['2']['b']='3'
	GraPh['3']['a']='1'
	GraPh['3']['b']='5'
	GraPh['4']['a']='4'
	GraPh['4']['b']='6'
	GraPh['5']['a']='7'
	GraPh['5']['b']='3'
	GraPh['6']['a']='4'
	GraPh['6']['b']='1'
	GraPh['7']['a']='4'
	GraPh['7']['b']='2'

	//判断集合
	res:=make([]map[byte]int,1)//定义结果集res[1],res[2]第1个集合，第2个集合
	//手动将初始集和终集加入结果集中
	mInit:=make(map[byte]int)
	mInit['1']=1
	mInit['2']=1
	mInit['3']=1
	mInit['4']=1
	mEnd:=make(map[byte]int)
	mEnd['5']=2
	mEnd['6']=2
	mEnd['7']=2
	res=append(res,mInit,mEnd)
	fmt.Printf("初始集：")
	PrintEnd(res)
	fmt.Println("-------------------------------")

	for{

		newSum:=make(map[byte]int)//定义个新的集合,代表新的节点通过路径到达的第几个集合
		for i:=1;i<len(res);i++{//遍历总集合
			for k:=range res[i]{
				tempByte:=GraPh[k]['a']//当前节点通过a路径到达的节点
				for j:=1;j<len(res);j++{//判断当前节点在哪个集合里
					if res[j][tempByte]!=0{
						newSum[k]=j
						break
					}
				}
			}
		}
		//fmt.Println(newSum)
		nowLength:=len(res)
		tempRes:=make([]map[byte]int,1)
		for i:=0;i<nowLength;i++{
			tempBs:=make([]byte,0)
			for index:=range res[i]{
				tempBs=append(tempBs,index)
			}
			tempDivide:=make([][]byte,0)
			tempDivide=append(tempDivide,divide(tempBs,newSum)...)
			tempRes=append(tempRes,getByteInt(tempDivide,len(tempRes))...)
		}
		res=tempRes
		//fmt.Println(res)
		if len(res)>nowLength{
			continue
		}

		newSum=make(map[byte]int)//定义个新的集合,代表新的节点通过路径到达的第几个集合
		for i:=0;i<len(res);i++{//遍历总集合
			for k:=range res[i]{
				tempByte:=GraPh[k]['b']//当前节点通过a路径到达的节点
				for j:=0;j<len(res);j++{//判断当前节点在哪个集合里
					if res[j][tempByte]!=0{
						newSum[k]=j
						break
					}
				}
			}
		}

		nowLength=len(res)
		tempRes=make([]map[byte]int,1)
		for i:=0;i<nowLength;i++{
			tempBs:=make([]byte,0)
			for index:=range res[i]{
				tempBs=append(tempBs,index)
			}
			tempDivide:=make([][]byte,0)
			tempDivide=append(tempDivide,divide(tempBs,newSum)...)
			tempRes=append(tempRes,getByteInt(tempDivide,len(tempRes))...)
		}
		res=tempRes
		if len(res)>nowLength{
			continue
		}
		break
	}
	fmt.Printf("结果集：")
	PrintRes(res,GraPh)
	fmt.Println("--------------------------------------")

}

func divide(bs []byte,newSum map[byte]int)[][]byte{//根据bs集合里面的元素分出来若干个集合
	nums:=make(map[int][]byte)
	for i:=0;i<len(bs);i++{
		nums[newSum[bs[i]]]=make([]byte,0)
	}
	ans:=make([][]byte,0)
	for i:=0;i<len(bs);i++{
		nums[newSum[bs[i]]]=append(nums[newSum[bs[i]]],bs[i])
	}
	for _,v:=range nums{
		ans=append(ans,v)
	}
	return ans
}

func getByteInt(divideBs [][]byte,index int)[]map[byte]int{
	res:=make([]map[byte]int,0)
	for i:=0;i<len(divideBs);i++{
		tempM:=make(map[byte]int)
		for j:=0;j<len(divideBs[i]);j++{
			tempM[divideBs[i][j]]=i+index
		}
		res=append(res,tempM)
	}
	return res
}

func PrintRes(res []map[byte]int,GraPh map[byte]map[byte]byte)  {
	ans:=make([][]int,0)
	for i:=1;i<len(res);i++{
		tempNums:=make([]int,0)
		for index:=range res[i]{
			tempNums=append(tempNums,int(index-'0'))
		}
		ans=append(ans,tempNums)
	}
	for i:=0;i<len(ans);i++{
		sort.Ints(ans[i])
	}
	sort.Slice(ans, func(i, j int) bool {
		if ans[i][0]<ans[j][0]{
			return true
		}
		return false
	})
	for i:=0;i<len(ans);i++{
		fmt.Printf("{")
		for j:=0;j<len(ans[i]);j++{
			if j==len(ans[i])-1{
				fmt.Printf("%d",ans[i][j])
				continue
			}
			fmt.Printf("%d,",ans[i][j])
		}
		if i==len(ans)-1{
			fmt.Printf("}")
			continue
		}
		fmt.Printf("},")
	}
	fmt.Println()
	numsFlag:=make(map[int][]int)
	numsFlagIndex:=make(map[int]byte)
	for i:=0;i<len(ans);i++{
		for j:=0;j<len(ans[i]);j++{
			numsFlagIndex[ans[i][j]]='A'+byte(i)
		}
		fmt.Printf("%s: ",string('A'+byte(i)))
		PrintSlice(ans[i])
		fmt.Println()
	}
	fmt.Println()
	for i:=0;i<len(ans);i++{
		for j:=0;j<len(ans[i]);j++{
			numsFlag[ans[i][j]]=ans[i]
		}
	}
	fmt.Println("集合","a","  b")
	for i:=0;i<len(ans);i++{
		//temp:=ans[i][0]
		fmt.Printf(string(numsFlagIndex[ans[i][0]]))
		fmt.Printf("   ")
		tempa:=int(GraPh[byte(ans[i][0])+'0']['a']-'0')
		fmt.Printf(string(numsFlagIndex[tempa]))
		fmt.Printf("   ")
		tempb:=int(GraPh[byte(ans[i][0])+'0']['b']-'0')
		fmt.Printf(string(numsFlagIndex[tempb]))
		fmt.Println()
	}
	fmt.Println()
	fmt.Println("---------------------------------")
	fmt.Println(" 集合"," -a-","-b-")
	for i:=0;i<len(ans);i++{
		//temp:=ans[i][0]
		PrintSlice(ans[i])
		fmt.Printf(" ")
		tempa:=int(GraPh[byte(ans[i][0])+'0']['a']-'0')
		PrintSlice(numsFlag[tempa])
		fmt.Printf(" ")
		tempb:=int(GraPh[byte(ans[i][0])+'0']['b']-'0')
		PrintSlice(numsFlag[tempb])
		fmt.Println()
	}

}
func PrintSlice(ans []int)  {
	fmt.Printf("{")
	for i:=0;i<len(ans);i++{
		if i==len(ans)-1{
			fmt.Printf("%d",ans[i])
			continue
		}
		fmt.Printf("%d,",ans[i])
	}
	fmt.Printf("}")
}
func PrintEnd(res []map[byte]int)  {
	ans:=make([][]int,0)
	for i:=1;i<len(res);i++{
		tempNums:=make([]int,0)
		for index:=range res[i]{
			tempNums=append(tempNums,int(index-'0'))
		}
		ans=append(ans,tempNums)
	}
	for i:=0;i<len(ans);i++{
		sort.Ints(ans[i])
	}
	sort.Slice(ans, func(i, j int) bool {
		if ans[i][0]<ans[j][0]{
			return true
		}
		return false
	})
	for i:=0;i<len(ans);i++{
		fmt.Printf("{")
		for j:=0;j<len(ans[i]);j++{
			if j==len(ans[i])-1{
				fmt.Printf("%d",ans[i][j])
				continue
			}
			fmt.Printf("%d,",ans[i][j])
		}
		if i==len(ans)-1{
			fmt.Printf("}")
			continue
		}
		fmt.Printf("},")
	}
	fmt.Println()
}